\section{Goal and path planning}
\subsection{Path planning algorithm : the A*}

The A* star algorithm is a informed search algorithm usable on graphs. It is based on a heuristic evaluation of the nodes.  Our implementation is based on fly distance. The idea is quite simple. There are two sets, one called open-set, containing the nodes which could be evaluated, the other, the closed-set, which contains all already evaluated node. The open set is sorted on the following value :
\begin{equation}
V = real\ best\ cost\ from\ source\ to\ node + heuristic\ value\ from\ node\ to\ goal.
\end{equation}
which means in our case : 
\begin{equation}
V = distance\ from\ source\ to\ node\ along\ best\ known\ path\ + distance\ between\ node\ and\ goal.
\end{equation}
In order to rebuild the path, a map is maintained, recording from which cell each cell has been directly reached.
\vspace*{0.7cm}

At each iteration, the first node in open set is evaluated. If it is the goal, the path is reconstructed. Else, its neighbors are retrieved, and their values computed. There are then add to the open set and to the map, and the current node is add to the closed set.
\vspace*{0.7cm}

The hardest part was to find the closest neighbors of a cell. In a usual grid this is only a matter of index. There, as the grid is built on a recursive way, neighbors don't always have the same depth.
\begin{figure}[h]
\center
\includegraphics[scale=0.5]{img/expand}
\caption{Direct neighbors of the black cell are represented in grey.}
\end{figure}

The main idea for determining the neighborhood of a cell is to find the closest parent which is in the same cell than the one which contains the neighbor. Diagonals are not considered as they may not be directly reachable. For example, here is how are retrieved the two bottom cells in the previous example :

\begin{figure}[h]
\center
\includegraphics[scale=0.3]{img/expand_all}
\end{figure}

\begin{enumerate}
\item First we need to find the smallest cell in which the neighbor is reachable. This is done by getting the parent until its coordinates are not at the bottom.
\item Then the closest cell with the same depth is searched. If there is none, the smallest reached cell is taken as neighbor. Else step 3 is executed.
\item If the cell has children, the ones which are adjacent to the current cell are recursively visited, and all smallest cells which are still adjacent to the current cell are selected.
\end{enumerate}